package basic.courseLearn12.problem;

import org.junit.Test;

//最长回文子序列
public class PalindromicSequence {
    @Test
    public void test(){
        String str = "acbdgsadfabcdffdcbsds";
        System.out.println(solution_violent(str));
        System.out.println(solution_manacher(str));
    }

    /**
     * 暴力法，枚举所有可能的回文子序列
     * @param str 字符串
     * @return 最长回文子序列
     */
    public String solution_violent(String str){

        // 1. 插入#，避免奇偶数长度的子序列
        str = insertChar(str, '#');
        // 2. 定义最大长度和此时的index
        int maxLength = -1, maxIndex = -1;
        // 3. 逐字符判断
        for (int i = 0; i < str.length(); i++) {
            // 3.1 得到当前字符的最长回文子序列长度
            int length = getPalindromeLength(str, i);
            // 3.2 判断是否大于最大长度
            if (length > maxLength) {
                maxLength = length;
                maxIndex = i;
            }
        }
        // 4. 得到最长回文子序列
        String result = "";
        for (int i = maxIndex - maxLength/2+1; i <= maxIndex + maxLength/2; i=i+2) {
            result += str.charAt(i);
        }
        return result;
    }

    /**
     * 使用manacher算法，时间复杂度O(n)
     * @param str 字符串
     * @return 最长回文子序列
     */
    public String solution_manacher(String str){
        //1. 定义变量，右边界，和当前的index
        int rightLimit = -1, currentIndex = -1;
        //2. 字符串插入#
        str = insertChar(str, '#');
        //3. 定义next数组，存储每个位置的最长回文半径
        int[] next = new int[str.length()];
        //4. 遍历字符串
        for (int i = 0; i < str.length(); i++) {
            //4.1 判断是否在边界外
            if (i > rightLimit) {
                //4.1.1 更新rightLimit，currentIndex，next[i]
                int length = getPalindromeLength(str, i);
                rightLimit = i + length/2 ;
                currentIndex = i;
                next[i] = length;
            }else{
                //4.2 寻找对称点
                int mirrorIndex = 2*currentIndex - i;
                //4.3 根据对称点的半径位置判断next[i]
                int mirrorLeftLimit = mirrorIndex - next[mirrorIndex]/2; //对称点左边界位置
                int centerLeftLimit = 2*currentIndex - rightLimit; //中心点左边界位置
                if (mirrorLeftLimit>centerLeftLimit){   //对称点左边界在中心点区域内部
                    next[i] = next[mirrorIndex];
                }else if(mirrorLeftLimit<centerLeftLimit){  //对称点左边界在中心点区域外部
                    next[i] = (rightLimit-i)*2 + 1;
                }else{  //对称点左边界在中心点区域上
                    //逐个判断
                    int left =i - next[mirrorIndex]/2 - 1;
                    int right = rightLimit + 1;
                    while(true) {
                        if (left < 0 || right >= str.length() || str.charAt(left)!= str.charAt(right)){
                            break;
                        }
                        left--;
                        right++;
                    }
                    next[i] = right - left - 1;
                    rightLimit = i + next[i]/2;
                    currentIndex = i;
                }
            }
        }
        //5. 得到最大值，并返回
        int maxValue = -1,maxIndex = -1;
        for (int i = 0; i < str.length(); i++) {
            if (next[i] > maxValue) {
                maxValue = next[i];
                maxIndex = i;
            }
        }
        String result = "";
        for (int i = maxIndex - next[maxIndex]/2+1; i <= maxIndex + next[maxIndex]/2; i=i+2) {
            result += str.charAt(i);
        }
        return result;
    }

    private int getPalindromeLength(String str, int i) {
        //1. 判断首尾
        if (i == 0 || i == str.length() - 1) {
            return 1;
        }
        //2. 定义左右指针
        int left =i, right = i;
        //3. 循环判断
        while(true){
            //3.1 左右指针向内移动
            left--;
            right++;
            if(left < 0 || right >= str.length()|| str.charAt(left)!= str.charAt(right)){
                break;
            }
        }
        return (right - left - 1);
    }

    /**
     * 插入字符，避免奇偶数长度的子序列
     * @param str 字符串
     * @param c 字符
     * @return 插入字符后的字符串
     */
    private String insertChar(String str, char c) {
        String result = ""+c;
        for (int i = 0; i < str.length(); i++) {
            result += str.charAt(i);
            result += c;
        }
        return result;
    }



}
